//
//  51_N皇后_优化.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/3.
//

import UIKit

class PlaceQueens1 {
    
    /// 标记每列是否有皇后
    var colums: [Bool] = []
    
    /// 标记左上角是否有皇后
    var leftTop: [Bool] = []
    
    /// 标记右上角是否有皇后
    var rightTop: [Bool] = []
//    摆放放回寺
    var placeCount = 0
    
    func solveNQueens(_ n: Int) {
        colums = Array(repeating: false, count: n)
        leftTop = Array(repeating: false, count: (n << 1) - 1)
        rightTop = Array(repeating: false, count: n * 2 - 1)

        place(0)
        print("\(n)皇后有\(placeCount)种摆放方式")
    }
    
    func place(_ row: Int) {
        if row == colums.count {
            placeCount += 1
            return
        }
//      回溯
        for colum in 0..<colums.count {
            if isAble(row, colum) {
                let ltIndex = row - colum  + (colums.count - 1)
                let rtIndex = row + colum
                leftTop[ltIndex] = true
                rightTop[rtIndex] = true
                colums[colum] = true
                
                place(row + 1)
                // 重置
                leftTop[ltIndex] = false
                rightTop[rtIndex] = false
                colums[colum] =  false
            }
        }
    }
    
    /// 当前位置都否可以摆放
    /// - Parameters:
    ///   - row: 行
    ///   - colum: 列
    /// - Returns: 结果
    func isAble(_ row: Int, _ colum: Int) -> Bool {
//        当前列有皇后
        if colums[colum] {
            return false
        }
//        斜线上是否有皇后
        let ltIndex = row - colum  + (colums.count - 1)
        let rtIndex = row + colum
        
        if leftTop[ltIndex] || rightTop[rtIndex] {
            return false
        }
        return true
    }
    
}

extension PlaceQueens1 {
    static func QA() {
        PlaceQueens1().solveNQueens(4) // 4皇后有2种
        PlaceQueens1().solveNQueens(8) // 8皇后有92种
    }
}
